In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, computational group theory is the study of
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
s by means of computers. It is concerned
with designing and analysing
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s and
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s to compute information about groups. The subject
has attracted interest because for many interesting groups
(including most of the
sporadic groups
In mathematics, a sporadic group is one of the 26 exceptional groups found in the classification of finite simple groups.
A simple group is a group ''G'' that does not have any normal subgroups except for the trivial group and ''G'' itself. Th ...
) it is impractical
to perform calculations by hand.
Important algorithms in computational group theory include:
* the
Schreier–Sims algorithm The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation c ...
for finding the
order of a
permutation group
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
* the
Todd–Coxeter algorithm In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group ''G'' by generators and relations and a subgroup ''H'' of ...
and
Knuth–Bendix algorithm for
coset enumeration In mathematics, coset enumeration is the problem of counting the cosets of a subgroup ''H'' of a group ''G'' given in terms of a presentation. As a by-product, one obtains a permutation representation for ''G'' on the cosets of ''H''. If ''H'' has ...
* the
product-replacement algorithm for finding random elements of a group
Two important
computer algebra system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s (CAS) used for group theory are
GAP and
Magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
. Historically, other systems such as CAS (for
character theory
In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about ...
) and
Cayley (a predecessor of Magma) were important.
Some achievements of the field include:
* complete enumeration of
all finite groups of order less than 2000
* computation of
representations
''Representations'' is an interdisciplinary journal in the humanities published quarterly by the University of California Press. The journal was established in 1983 and is the founding publication of the New Historicism movement of the 1980s. It ...
for all the
sporadic groups
In mathematics, a sporadic group is one of the 26 exceptional groups found in the classification of finite simple groups.
A simple group is a group ''G'' that does not have any normal subgroups except for the trivial group and ''G'' itself. Th ...
See also
*
Black box group
In computational group theory, a black box group (black-box group) is a group ''G'' whose elements are encoded by bit strings of length ''N'', and group operations are performed by an oracle (the "black box"). These operations include:
• takin ...
References
*
surveyof the subject by Ákos Seress from
Ohio State University
The Ohio State University, commonly called Ohio State or OSU, is a public land-grant research university in Columbus, Ohio. A member of the University System of Ohio, it has been ranked by major institutional rankings among the best publ ...
, expanded from an article that appeared in the
Notices of the American Mathematical Society
''Notices of the American Mathematical Society'' is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue. The first volume appeared in 1953. Each issue of the magazine since ...
is available online. There is also
surveyby
Charles Sims Charles Sims may refer to:
* Charles Sims (painter) (1873–1928), British painter
* Charles Sims (mathematician) (1938–2017), American mathematician
* Charles Sims (aviator) (1899–1929), British World War I flying ace
* Charles Sims (American ...
from
Rutgers University
Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's ...
and a
older surveyby Joachim Neubüser from
RWTH Aachen
RWTH Aachen University (), also known as North Rhine-Westphalia Technical University of Aachen, Rhine-Westphalia Technical University of Aachen, Technical University of Aachen, University of Aachen, or ''Rheinisch-Westfälische Technische Hoch ...
.
There are three books covering various parts of the subject:
* Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, "Handbook of computational group theory", Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005.
*
Charles C. Sims
Charles Coffin Sims (April 14, 1937 – October 23, 2017J. J. O'Connor and E. F. Robertson''Charles Sims biography'' MacTutor History of Mathematics archive. Accessed 2018-12-20.) was an American mathematician best known for his work in group t ...
, "Computation with Finitely-presented Groups", Encyclopedia of Mathematics and its Applications, vol 48,
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press
A university press is an academic publishing hou ...
, Cambridge, 1994.
* Ákos Seress, "Permutation group algorithms", Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. {{ISBN, 0-521-66103-X.
Computational fields of study